package pers.qianyu.month_202012.date_20201230;

import org.junit.*;

/**
 * 63. 不同路径 II
 * https://leetcode-cn.com/problems/unique-paths-ii/
 *
 * @author mizzle rain
 * @date 2020-12-30 19:32
 */
public class UniquePathsWithObstacles {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int h = obstacleGrid.length;
        int w = obstacleGrid[0].length;
        // dp[i][j] 表示走到 i,j 这个格子的时候，有几种方案
        int[][] dp = new int[h][w];
        for (int i = 0; i < h; i++) {
            if (obstacleGrid[i][0] == 1) break;
            dp[i][0] = 1;
        }
        if (dp[0][0] == 0) {
            return 0;
        }
        for (int j = 1; j < w; j++) {
            if (obstacleGrid[0][j] == 1) break;
            dp[0][j] = 1;
        }
        for (int i = 1; i < h; i++) {
            for (int j = 1; j < w; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        //ArrayUtil.printDeepToString(dp);
        return dp[h - 1][w - 1];
    }

    @Test
    public void test1() {
        int[][] obstacleGrid = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        int result = new UniquePathsWithObstacles().uniquePathsWithObstacles(obstacleGrid);
        Assert.assertEquals(result, 2);
    }

    @Test
    public void test2() {
        int[][] obstacleGrid = {{0, 1}, {0, 0}};
        int result = new UniquePathsWithObstacles().uniquePathsWithObstacles(obstacleGrid);
        Assert.assertEquals(result, 1);
    }
}
